/**
 * Alipay.com Inc.
 * Copyright (c) 2004-2021 All Rights Reserved.
 */
package primary.primary0;

/**
 * 同S1003搜素旋转数组
 *
 * 首先定义一下数组的旋转, 旋转就是左右移动。。。如下, 就挺突然的。
 * https://blog.csdn.net/u012371712/article/details/79683390
 * 旋转能给一个数组带来怎样的变化?所以旋转n次和1次有什么区别?
 */
public class S0033搜素旋转数组 {


    /**
     * 答案的二分法方式
     * 两个指针l r，分别往中间跑
     * 1. 根据mid与nums[0]的关系，判断当前是在左边那条递增序列上还是右边那条
     * 2. 根据mid，和nums[l],nums[r]的大小关系，排除一半的位置，也就是二分法
     */
    class Solution {
        public int search(int[] nums, int target) {
            int n = nums.length;
            if (n == 0) {
                return -1;
            }
            if (n == 1) {
                return nums[0] == target ? 0 : -1;
            }
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[0] <= nums[mid]) {
                    if (nums[0] <= target && target < nums[mid]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                } else {
                    if (nums[mid] < target && target <= nums[n - 1]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }
    }




    /**
     * 100, 关于二分法, 中间值一直处理不好。这里就一直不用endPosi, 所以取midPosi的时候不用考虑太多。
     *
     * 这个方法是两边都找一下，endPosi不取值
     *
     * 边界处理得比示范要好一点点。
     */
    public int search2(int[] arr, int target) {
        return binSearch(arr, target, 0, arr.length);
    }
    // endPosi是取不到的。
    private int binSearch(int[] arr, int target, int startPosi, int endPosi){
        //System.out.println(Arrays.toString(arr) + startPosi + "|" + endPosi);
        if(endPosi - startPosi <= 1) return arr[startPosi] == target? startPosi: -1;
        if(arr[startPosi] < arr[endPosi - 1]){
            // 这是一段递增的
            if(target > arr[endPosi - 1] || target < arr[startPosi]) return -1;
        }
        int midPosi = (endPosi + startPosi) / 2;
        int a = binSearch(arr, target, startPosi, midPosi);
        if(a != -1) return a;
        return binSearch(arr, target, midPosi, endPosi);
    }

    /**
     * 25, 遍历, 这样肯定不行的。
     */
    public int search(int[] arr, int target) {
        for(int i = 0; i < arr.length; i++){
            if(arr[i] == target) return i;
        }
        return -1;
    }
}